package Algorithm.search;

import java.util.TreeMap;

/**
 * 704. 二分查找 https://leetcode.cn/problems/binary-search/
 * 参考讲解视频：https://www.bilibili.com/video/BV1d54y1q7k7
 * 题目简述：给定一个n个元素升序整型数组 nums，若目标值target存在则返回其下标，否则返回-1
 * 二分查找过程中的循环不变量：无论对于严格升序数组还是非递减数组，在查找过程中始终满足：low指针左边的元素都是小于target，high指针右边元素都是大于target
 */
public class BinarySearch {

    /**
     * 思路：双指针。初始时low指向数组开头，high指向数组末尾，当low <= high时循环取mid比较并更新low或high的位置
     */
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length-1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) return mid;
            //若mid元素小于target，则移动low指针到mid+1
            else if (nums[mid] < target) low = mid + 1;
            //若mid元素大于target，则移动low指针到mid-1
            else high = mid - 1;
        }
        return -1;
    }

    /**
     * 思路二：使用TreeMap完成二分查找
     */
    public int search2(int[] nums, int target) {
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i = 0;i < nums.length;i++)
            treeMap.put(nums[i], i);
        return treeMap.getOrDefault(target, -1);
    }
}
